package leetcode_300;

import java.util.LinkedList;

/**
 *@author 周杨
 *SlidingWindowMaximum_239_ 给定一个数组 和窗口大小  输出一个数组 里面存的是每个窗口的最大值
 *describe:用双向队列 。当我们遇到新的数时，将新的数和双向队列的末尾比较，
 *如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才住手
 *。这样，我们可以保证队列里的元素是从头到尾降序的 每次判断队列头的数是否越界 如果越界 
 *则出队列 也保证队列里的数都是有效数  AC 66%
 *2018年6月25日 下午7:15:58
 */
public class SlidingWindowMaximum_239_ {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        LinkedList<Integer> deque = new LinkedList<Integer>();
        int[] res = new int[nums.length + 1 - k];
        for(int i = 0; i < nums.length; i++){
            // 每当新数进来时，如果发现队列头部的数的下标，是窗口最左边数的下标，则扔掉
            if(!deque.isEmpty() && deque.peekFirst() == i - k) deque.poll();
            // 把队列尾部所有比新数小的都扔掉，保证队列是降序的
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.removeLast();
            // 加入新数
            deque.offerLast(i);
            // 队列头部就是该窗口内第一大的
            if((i + 1) >= k) res[i + 1 - k] = nums[deque.peek()];
        }
        return res;
    }
}
